package com.ayuer.chapter08;

import java.util.Arrays;

public class MergeSortDemo {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 2, 4, 10, 11};
        split(arr, 0, arr.length - 1, new int[arr.length]);
        System.out.println(Arrays.toString(arr));

//        merge(arr, 0, 2, 3, arr.length - 1, new int[arr.length]);
//        System.out.println(Arrays.toString(arr));
    }

    //合并两个有序数组
    //{2，4，6}
    //{1，3，5}
    //采用双指针
    public static void merge(int[] arr, int iStart, int iEnd, int jStart, int jEnd, int[] tmp) {
        int i = iStart, j = jStart;
        int k = iStart;
        while (i <= iEnd && j <= jEnd) {
            if (arr[i] < arr[j]) {//j大
                tmp[k++] = arr[i++];
            } else {
                tmp[k++] = arr[j++];
            }
//            k++;
        }

        // 合并剩余部分
        if (i <= iEnd) {
            System.arraycopy(arr, i, tmp, k, iEnd - i + 1);
        }
        if (j <= jEnd) {
            System.arraycopy(arr, j, tmp, k, jEnd - j + 1);
        }
    }

    public static void split(int[] arr, int left, int right, int[] tmp) {
        //治
        if (left == right) {
            //只有一个数据就不用切分了
            return;
        }

        //分
        int middle = (left + right) >>> 1;
        split(arr, left, middle, tmp);
        split(arr, middle + 1, right, tmp);

        //合
        merge(arr, left, middle, middle + 1, right, tmp);
        // 把合并结果写回 arr
        System.arraycopy(tmp, left, arr, left, right - left + 1);

    }
}
